package com.datastructure.test.combineofphonenumber;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;

public class CombineOfPhoneNumber {

    public static void main(String[] args) {
        CombineOfPhoneNumber combineOfPhoneNumber = new CombineOfPhoneNumber();
        ArrayList<String> arrayList = combineOfPhoneNumber.phoneNumber("3");
        System.out.println(arrayList);
    }

    public StringBuilder stringBuilder;
    public ArrayList<String> phoneNumber (String num) {
        // write code here
        HashMap<String,String> map = new HashMap<>();
        map.put("2","ABC");
        map.put("3","DEF");
        map.put("4","GHI");
        map.put("5","JKL");
        map.put("6","MNO");
        map.put("7","PQRS");
        map.put("8","TUV");
        map.put("9","WXYZ");
        int length = num.length();
        String[] split = num.split("");
        ArrayList<String> res = new ArrayList<>();
        LinkedList<Character> linkedList = new LinkedList<>();
        dfs(0,split,map,res,linkedList,length);
        return res;
    }

    private void dfs(int start, String[] split, HashMap<String, String> map, ArrayList<String> res, LinkedList<Character> linkedList, int length) {
        if(linkedList.size()==length){
            stringBuilder=new StringBuilder();
            for (Character character : linkedList) {
                stringBuilder.append(character);
            }
            res.add(stringBuilder.toString());
            return;
        }
        String key = split[start];
        String valueString = map.get(key);
        char[] charArray = valueString.toCharArray();
        for (char c : charArray) {
            linkedList.add(c);
            dfs(start + 1, split, map, res, linkedList, length);
            linkedList.removeLast();
        }
    }

    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    ArrayList<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public ArrayList<String> phoneNumber2 (String num) {
        // write code here
        backTracking(num, 0);
        return res;
    }

    public void backTracking(String num, int index) {
        if (index == num.length()) {
            res.add(sb.toString());
            return;
        }

        int digit = num.charAt(index) - '0';
        String str = numString[digit];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backTracking(num, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
